package com.wujunshen.algorithm.leetcode.basic;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/2 22:23<br>
 */
@Slf4j
public class Trie {
  private final TrieNode1 root;

  public Trie() {
    root = new TrieNode1();
  }

  public void insert(String word) {
    TrieNode1 current = root;
    for (char c : word.toCharArray()) {
      if (current.getChild(c - 'a') == null) {
        current.setChild(c - 'a', new TrieNode1());
      }
      current = current.getChild(c - 'a');
    }
    current.setItem(word);
  }

  public boolean search(String word) {
    TrieNode1 current = root;
    for (char c : word.toCharArray()) {
      if (current.getChild(c - 'a') == null) {
        return false;
      }
      current = current.getChild(c - 'a');
    }
    return current.getItem().equals(word);
  }

  public boolean startsWith(String prefix) {
    TrieNode1 current = root;
    for (char c : prefix.toCharArray()) {
      if (current.getChild(c - 'a') == null) {
        return false;
      }
      current = current.getChild(c - 'a');
    }
    return true;
  }

  public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("apple");
    // 返回 True
    boolean result = trie.search("apple");
    log.info("result is:{}", result);
    // 返回 False
    result = trie.search("app");
    log.info("result is:{}", result);
    // 返回 True
    result = trie.startsWith("app");
    log.info("result is:{}", result);
    trie.insert("app");
    // 返回 True
    result = trie.search("app");
    log.info("result is:{}", result);
  }
}

@Data
class TrieNode1 {
  private static final int CHILDREN_SIZE = 26;
  private final TrieNode1[] children;
  private String item;

  public TrieNode1() {
    children = new TrieNode1[CHILDREN_SIZE];
    item = "";
  }

  public TrieNode1 getChild(int i) {
    if (i >= CHILDREN_SIZE || i < 0) {
      return null;
    }
    return children[i];
  }

  public void setChild(int i, TrieNode1 node) {
    children[i] = node;
  }
}
